<!DOCTYPE html>
<html lang=zh-CN>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI" />
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta property="og:description" content="samuel-24276的博客">
    <meta property="og:type" content="website">
    <meta name="description" content="samuel-24276的博客">
    <meta name="keyword"  content="aircloud">
    <link rel="shortcut icon" href="/myblog/img/favicon.ico">

    <title>
        
        QMap vs. QHash-A small benchmark - samuel-24276的博客 | samuel-24276&#39;s Blog
        
    </title>

    <!-- Custom CSS -->
    
<link rel="stylesheet" href="/myblog/css/aircloud.css">

    
<link rel="stylesheet" href="/myblog/css/gitment.css">

    <!--<link rel="stylesheet" href="https://imsun.github.io/gitment/style/default.css">-->
    <link href="//at.alicdn.com/t/font_620856_28hi1hpxx24.css" rel="stylesheet" type="text/css">
    <!-- ga & ba script hoook -->
    <script></script>
<meta name="generator" content="Hexo 7.1.1"></head>

<body>

<div class="site-nav-toggle" id="site-nav-toggle">
    <button>
        <span class="btn-bar"></span>
        <span class="btn-bar"></span>
        <span class="btn-bar"></span>
    </button>
</div>

<div class="index-about">
    <i> Like what you do, do what you like </i>
</div>

<div class="index-container">
    
    <div class="index-left">
        
<div class="nav" id="nav">
    <div class="avatar-name">
        <div class="avatar ">
            <img src="/myblog/img/avatar.jpg" />
        </div>
        <div class="name">
            <i>samuel-24276</i>
        </div>
    </div>
    <div class="contents" id="nav-content">
        <ul>
            <li >
                <a href="/myblog/">
                    <i class="iconfont icon-shouye1"></i>
                    <span>主页</span>
                </a>
            </li>
            <li >
                <a href="/myblog/tags">
                    <i class="iconfont icon-biaoqian1"></i>
                    <span>标签</span>
                </a>
            </li>
            <li >
                <a href="/myblog/archives">
                    <i class="iconfont icon-guidang2"></i>
                    <span>存档</span>
                </a>
            </li>
            <li >
                <a href="/myblog/collect/">
                    <i class="iconfont icon-shoucang1"></i>
                    <span>收藏</span>
                </a>
            </li>
            <li >
                <a href="/myblog/about/">
                    <i class="iconfont icon-guanyu2"></i>
                    <span>关于</span>
                </a>
            </li>
            
            <li>
                <a id="search">
                    <i class="iconfont icon-sousuo1"></i>
                    <span>搜索</span>
                </a>
            </li>
            
        </ul>
    </div>
    
        <div id="toc" class="toc-article">
    <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#Under-The-Hood"><span class="toc-text">Under The Hood</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#The-Benchmark%E5%9F%BA%E5%87%86%E6%B5%8B%E8%AF%95"><span class="toc-text">The Benchmark基准测试</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#The-Result"><span class="toc-text">The Result</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#Qt-4-8"><span class="toc-text">Qt 4.8</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Qt-5"><span class="toc-text">Qt 5</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Conclusion"><span class="toc-text">Conclusion</span></a></li></ol>
</div>
    
</div>


<div class="search-field" id="search-field">
    <div class="search-bg" id="search-bg"></div>
    <div class="search-container">
        <div class="search-input">
            <span id="esc-search"> <i class="icon-fanhui iconfont"></i></span>
            <input id="search-input"/>
            <span id="begin-search">搜索</span>
        </div>
        <div class="search-result-container" id="search-result-container">

        </div>
    </div>
</div>

        <div class="index-about-mobile">
            <i> Like what you do, do what you like </i>
        </div>
    </div>
    
    <div class="index-middle">
        <!-- Main Content -->
        


<div class="post-container">
    <div class="post-title">
        QMap vs. QHash-A small benchmark
    </div>

    <div class="post-meta">
        <span class="attr">发布于：<span>2021-05-13 09:05:21</span></span>
        
        <span class="attr">标签：/
        
        <a class="tag" href="/myblog/tags/#Qt" title="Qt">Qt</a>
        <span>/</span>
        
        <a class="tag" href="/myblog/tags/#数据结构" title="数据结构">数据结构</a>
        <span>/</span>
        
        <a class="tag" href="/myblog/tags/#文章翻译" title="文章翻译">文章翻译</a>
        <span>/</span>
        
        
        </span>
        <span class="attr">访问：<span id="busuanzi_value_page_pv"></span>
</span>
</span>
    </div>
    <div class="post-content no-indent">
        <p>在2012年Qt开发者日(QtCore)的演讲中，我做了一个比较QMap和QHash的基准测试。我认为在这篇简短的博客文章中分享结果会很好。</p>
<h1 id="Under-The-Hood"><a href="#Under-The-Hood" class="headerlink" title="Under The Hood"></a>Under The Hood</h1><p><code>QHash</code>是用哈希表实现的，<code>QMap</code>是用Qt4中的跳表实现的。</p>
<p>在Qt 5中，容器的实现有了一些变化，但概念仍然是相同的。以下是主要的区别:</p>
<ul>
<li><code>QVector</code>, <code>QString</code>和<code>QByteArray</code>现在共享相同的实现(<code>QArrayData</code>)。主要的区别是现在有一个偏移量，将来可能允许引用外部数据。</li>
<li><code>QMap</code>实现已经完全改变了。它不再是一个跳表，而是一个红黑树。</li>
</ul>
<h1 id="The-Benchmark基准测试"><a href="#The-Benchmark基准测试" class="headerlink" title="The Benchmark基准测试"></a>The Benchmark基准测试</h1><p>基准测试很简单，在一秒钟内在循环中执行大量查找并计算迭代次数。<br>这并不科学。目标只是显示曲线的形状。</p>
<p>The source: <a target="_blank" rel="noopener" href="https://woboq.com/blog/qmap_qhash_benchmark/benchmark.cc.html">benchmark.cc</a></p>
<h1 id="The-Result"><a href="#The-Result" class="headerlink" title="The Result"></a>The Result</h1><p>在我的计算机上运行gcc 4.7。越高越好。元素的数量以对数为单位。对于QHash，应该期望它不随元素数量的变化而变化，而对于QMap，它应该是O(log N):对数刻度上的一条直线。</p>
<h2 id="Qt-4-8"><a href="#Qt-4-8" class="headerlink" title="Qt 4.8"></a>Qt 4.8</h2><p><img src="https://woboq.com/blog/qmap_qhash_benchmark/bench-48.png"></p>
<p>QMap执行速度比std::map稍慢。对于少于10个元素，QMap查找速度比QHash快。</p>
<h2 id="Qt-5"><a href="#Qt-5" class="headerlink" title="Qt 5"></a>Qt 5</h2><p><img src="https://woboq.com/blog/qmap_qhash_benchmark/bench-5.png"></p>
<p>将跳表改为红黑树是个好主意。与STL相比，Qt容器的性能是相同的。如果元素少于20个，QMap比QHash快。</p>
<p>如果你比较Qt5和Qt4之间的数字，你会发现Qt5表现得更好。这可能与QString的变化有关。</p>
<h1 id="Conclusion"><a href="#Conclusion" class="headerlink" title="Conclusion"></a>Conclusion</h1><p>典型的规则是:<strong>仅在需要对项目进行排序</strong>或您知道您的<strong>映射中总是有非常少量的项目</strong>时使用QMap。</p>
<hr>

        
            <div class="donate-container">
    <div class="donate-button">
        <button id="donate-button">赞赏</button>
    </div>
    <div class="donate-img-container hide" id="donate-img-container">
        <img id="donate-img" src="" data-src="/myblog/img/donate.jpg">
        <p> 感谢鼓励 </p>
    </div>
</div>
        
        <br />
        <div id="comment-container">
        </div>
        <div id="disqus_thread"></div>
        <div id="lv-container"></div>
        <div class="giscus"></div>
    </div>
</div>

    </div>
</div>


<footer class="footer">
    <ul class="list-inline text-center">
        
        

        

        

        
        <li>
            <a target="_blank"  href="https://github.com/samuel-24276">
                            <span class="fa-stack fa-lg">
                                <i class="iconfont icon-github"></i>
                            </span>
            </a>
        </li>
        

        

    </ul>
    
    <p>
        <span>/</span>
        
        <span><a target="_blank" rel="noopener" href="https://github.com/samuel-24276">samuel-24276&#39;s Page</a></span>
        <span>/</span>
        
        <span><a target="_blank" rel="noopener" href="https://beian.miit.gov.cn/">北京-未备案</a></span>
        <span>/</span>
        
        <span><a href="#">返回顶部</a></span>
        <span>/</span>
        
    </p>
    
    <p>
        <span id="busuanzi_container_site_pv">
            <span id="busuanzi_value_site_pv"></span>PV
        </span>
        <span id="busuanzi_container_site_uv">
            <span id="busuanzi_value_site_uv"></span>UV
        </span>
        Created By <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a>  Theme <a target="_blank" rel="noopener" href="https://github.com/aircloud/hexo-theme-aircloud">AirCloud</a></p>
</footer>




</body>

<script>
    // We expose some of the variables needed by the front end
    window.hexo_search_path = "search.json"
    window.hexo_root = "/myblog/"
    window.isPost = true
</script>
<script src="https://cdn.bootcss.com/jquery/3.3.1/jquery.min.js"></script>

<script src="/myblog/js/index.js"></script>

<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>






    <script type="text/javascript">
       (function() {
           if (typeof LivereTower === 'function') { return; }

           var j, d = document.getElementById('lv-container');

           d.setAttribute('data-id','city');
           d.setAttribute('data-uid' , 'MTAyMC80OTA5OC8yNTU5Mw==');

           j = document.createElement('script');
           j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
           j.async = true;

           d.appendChild(j);
       })();
    </script>
    <noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
    </div>

</html>
